package zuochengyun;

import java.util.HashMap;
import java.util.Map.Entry;

//出现次数的TopK问题
public class TopKOfTimes {

	// 使用堆的方式来完成
	private class HeapNode {
		public String str;	// 值
		public int times; // 来自哪个数组

		public HeapNode(String str, int times) {
			this.str = str;
			this.times = times;
		}
	}

	//按照出现次数打印
	public void printTopKAndRank(String[] arr, int k) {
		if(arr == null || k < 1){
			return;
		}
		HashMap<String, Integer> map = new HashMap<>();
		String temp;
		for (int i = 0; i < arr.length; i++) {
			temp = arr[i];
			if(map.containsKey(temp)){
				map.put(temp, map.get(temp) + 1);
			}else{
				map.put(temp, 1);
			}
		}
		// 首先建立一个N个元素的小跟堆
		HeapNode[] heap = new HeapNode[k];
		int index = 0;
		for (Entry<String, Integer> entry : map.entrySet()) {
			String key = entry.getKey();
			int times = entry.getValue();
			HeapNode node = new HeapNode(key, times);
			if(index != k){
				//如果堆还没有k个元素
				heap[index] = node;
				heapCreate(heap, index++);
			}else{
				//如果已满并且结点的次数大于头结点，就将头结点更换并对堆进行调整
				if(heap[0].times < node.hashCode()){
					heap[0] = node;
					heapAdjust(heap, 0, k);
				}
			}
		}
		//进行堆排序,从大到小的顺序
		for (int i = index - 1; i != 0; i--) {
			swap(heap, 0, i);
			heapAdjust(heap, 0, i);
		}
	}

	private void heapAdjust(HeapNode[] heap, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int small = index;
		while (left < heapSize) {
			if (heap[left].times < heap[index].times) {
				small = left;
			}
			if (right < heapSize && heap[right].times < heap[left].times) {
				small = right;
			}
			if (small != index) {
				swap(heap, index, small);
			} else {
				break;
			}
			index = small;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}

	public void heapCreate(HeapNode[] heap, int index) {
		while (index != 0) {
			int parent = (index - 1) / 2;
			if (heap[parent].times > heap[index].times) {
				swap(heap, parent, index);
				index = parent;
			} else {
				break;
			}
		}
	}

	public void swap(HeapNode[] heap, int parent, int index) {
		HeapNode temp = heap[parent];
		heap[parent] = heap[index];
		heap[index] = temp;
	}
	
		
}
